package leetcode_周赛._2022._202201._30;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/30 1:24
 */
public class _5994 {
    public static void main(String[] args) {
        System.out.println(new _5994().subStrHash("xmmhdakfursinye", 96, 45, 15, 21));
    }

    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int m = s.length();
        int[] nums = new int[m];
        for (int i = 0; i < m; i++) nums[i] = s.charAt(i) - 'a' + 1;
        int i = 0;
        for (; i <= m - k; i++) {
            long tmp = 0, p = 1;
            String ans = "";
            for (int j = i; j < i + k; j++) {
                tmp += nums[j] * p;
                p *= power;
                ans += s.charAt(j);
            }
            if (tmp % modulo == hashValue) return ans;
        }
        return "";
    }

}
